class Solution
{
public:
    vector<string> ambiguousCoordinates(string s)
    {
        int n = s.size();
        vector<string> result;
        auto push_coordinate = [&](string &numStr1, string &numStr2)
        {
            result.push_back("(" + numStr1 + ", " + numStr2 + ")");
        };
        for (int commaPos = 2; commaPos < n - 1; ++commaPos)
        {
            string leftNumStr(s.begin() + 1, s.begin() + commaPos);
            string rightNumStr(s.begin() + commaPos, s.end() - 1);

            if (validInt(leftNumStr))
            {
                if (validInt(rightNumStr))
                {
                    push_coordinate(leftNumStr, rightNumStr);
                }
                for (int dotPos = 1; dotPos < rightNumStr.size(); ++dotPos)
                {
                    if (validFloat(rightNumStr, dotPos))
                    {
                        string floatNumStr = rightNumStr;
                        floatNumStr.insert(dotPos, ".");
                        push_coordinate(leftNumStr, floatNumStr);
                    }
                }
            }
            for (int dotPosL = 1; dotPosL < leftNumStr.size(); ++dotPosL)
            {
                if (validFloat(leftNumStr, dotPosL))
                {
                    string leftFloatStr = leftNumStr;
                    leftFloatStr.insert(dotPosL, ".");
                    if (validInt(rightNumStr))
                    {
                        push_coordinate(leftFloatStr, rightNumStr);
                    }
                    for (int dotPosR = 1; dotPosR < rightNumStr.size(); ++dotPosR)
                    {
                        if (validFloat(rightNumStr, dotPosR))
                        {
                            string rightFloatStr = rightNumStr;
                            rightFloatStr.insert(dotPosR, ".");
                            push_coordinate(leftFloatStr, rightFloatStr);
                        }
                    }
                }
            }
        }
        return result;
    }

    bool validInt(string &s)
    {
        if (s.size() == 1)
        {
            return true;
        }
        return s[0] != '0';
    }

    bool validFloat(string &s, int dotPos)
    {
        if (dotPos <= 0 || dotPos >= s.size())
        {
            return false;
        }
        if (dotPos > 1 && s[0] == '0')
        {
            return false;
        }
        return s[s.size() - 1] != '0';
    }
};